#include <dbg.h>
#include <gtest/gtest.h>
using namespace std;

#ifdef FAST
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) {
            return nullptr;  // 空节点的根是其本身
        }
        if (root == p || root == q) {
            return root;  // 目标节点本身也是其根
        }

        if (p->val < root->val && q->val > root->val) {
            return root;
        } else if (p->val > root->val && q->val < root->val) {
            return root;
        }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left == nullptr && right != nullptr) {
            return right;
        }
        if (left != nullptr && right == nullptr) {
            return left;
        }

        return nullptr;
    }
};
#else
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int rootVal = root->val;
        if (rootVal > p->val &&
            rootVal > q->val) {  // p q 都在左子树, 递归左子树
            return lowestCommonAncestor(root->left, p, q);
        }
        if (rootVal < p->val &&
            rootVal < q->val) {  // p q 都在右子树, 递归右子树
            return lowestCommonAncestor(root->right, p, q);
        }
        return root;
    }
};
#endif

TEST(TEST1, lowestCommonAncestor) {
    Solution s;

    TreeNode* root = nullptr;
    TreeNode* p = nullptr;
    TreeNode* q = nullptr;
    TreeNode* ans = nullptr;

    root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    p = root->left;
    q = root->right;
    ans = root;
    EXPECT_EQ(s.lowestCommonAncestor(root, p, q), ans);
}

TEST(TEST2, lowestCommonAncestor) {
    Solution s;

    TreeNode* root = nullptr;
    TreeNode* p = nullptr;
    TreeNode* q = nullptr;
    TreeNode* ans = nullptr;

    root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    p = root->left;
    q = root->left->right;
    ans = root->left;
    EXPECT_EQ(s.lowestCommonAncestor(root, p, q), ans);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}